package com.yx.study.leet.questionList.questions;

import org.junit.Test;

/**
 * 35. 搜索插入位置
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * https://leetcode.cn/problems/search-insert-position/
 * */
public class Solution35 {
    public int searchInsert(int[] nums, int target) {
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        while (left <= right) {
            int mid = ((right - left) >> 1) + left;
            if (target <= nums[mid]) {
                ans = mid; // 记录中位数下标, 如果不存在 则是插入下标
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
        return ans;
    }

    @Test
    public void test(){
        int[] nums = new int[]{1,3,5,6};
        System.out.println(searchInsert(nums, 7));
    }

    public int CompromiseSorting(int[] nums,int target){
        int n = nums.length;
        int left = 0, right = n - 1, ans = n;
        int middle = 0;
        while (left<=right){
            middle = (right-left)>>1 +left;
            if (target<nums[middle]){
                right = middle-1;
            }else if (target>nums[middle]){
                left = middle+1;
            }else {
                return middle;
            }
        }
        return -1; // 数组中没有对应的值,返回-1
    }
}
